{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Maximum Non-decreasing Array Length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #queue #array #binary-search #dynamic-programming #monotonic-queue #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #队列 #数组 #二分查找 #动态规划 #单调队列 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximumLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最大非递减数组的长度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>你可以执行任意次操作。每次操作中，你需要选择一个 <strong>子数组</strong>&nbsp;，并将这个子数组用它所包含元素的 <strong>和</strong>&nbsp;替换。比方说，给定数组是&nbsp;<code>[1,3,5,6]</code>&nbsp;，你可以选择子数组&nbsp;<code>[3,5]</code>&nbsp;，用子数组的和 <code>8</code>&nbsp;替换掉子数组，然后数组会变为&nbsp;<code>[1,8,6]</code>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回执行任意次操作以后，可以得到的 <strong>最长非递减</strong>&nbsp;数组的长度。</p>\n",
    "\n",
    "<p><strong>子数组</strong>&nbsp;指的是一个数组中一段连续 <strong>非空</strong>&nbsp;的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [5,2,2]\n",
    "<b>输出：</b>1\n",
    "<strong>解释：</strong>这个长度为 3 的数组不是非递减的。\n",
    "我们有 2 种方案使数组长度为 2 。\n",
    "第一种，选择子数组 [2,2] ，对数组执行操作后得到 [5,4] 。\n",
    "第二种，选择子数组 [5,2] ，对数组执行操作后得到 [7,2] 。\n",
    "这两种方案中，数组最后都不是 <strong>非递减</strong>&nbsp;的，所以不是可行的答案。\n",
    "如果我们选择子数组 [5,2,2] ，并将它替换为 [9] ，数组变成非递减的。\n",
    "所以答案为 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,2,3,4]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>数组已经是非递减的。所以答案为 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [4,3,2,6]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>将 [3,2] 替换为 [5] ，得到数组 [4,5,6] ，它是非递减的。\n",
    "最大可能的答案为 3 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-maximum-non-decreasing-array-length](https://leetcode.cn/problems/find-maximum-non-decreasing-array-length/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-maximum-non-decreasing-array-length](https://leetcode.cn/problems/find-maximum-non-decreasing-array-length/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,2]', '[1,2,3,4]', '[4,3,2,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, a: List[int]) -> int:\n",
    "        \n",
    "        n = len(a)\n",
    "        s = list(accumulate(a,initial=0))\n",
    "        f = [0] * (n + 1)\n",
    "        last = [0] * (n + 1)\n",
    "        q = deque([0])\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            while len(q) > 1 and s[q[1]]+last[q[1]] <= s[i]:\n",
    "                q.popleft()\n",
    "            \n",
    "            f[i] = f[q[0]] + 1\n",
    "            last[i] = s[i] - s[q[0]]\n",
    "            \n",
    "            while q and s[i] + last[i] <= s[q[-1]] + last[q[-1]]:\n",
    "                q.pop()\n",
    "            \n",
    "            q.append(i)\n",
    "        # print(f)\n",
    "        # print(last)\n",
    "        return f[n]\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            nums[i] += nums[i - 1]\n",
    "        nums.insert(0, 0)\n",
    "        dp = [0] * (n + 1)\n",
    "        test = [0] * (n + 1)\n",
    "        q = deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            while len(q) > 1 and nums[q[1]] + test[q[1]] <= nums[i]:\n",
    "                q.popleft()\n",
    "            dp[i] = dp[q[0]] + 1\n",
    "            test[i] = nums[i] - nums[q[0]]\n",
    "            while q and nums[q[-1]] + test[q[-1]] >= nums[i] + test[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        best = deque([(0, 0, 0)])\n",
    "        s = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            s += v\n",
    "            while len(best) > 1 and best[1][0] <= s:\n",
    "                best.popleft()\n",
    "            a = (s + s - best[0][1], s, best[0][2] + 1)\n",
    "            while best and best[-1][0] >= a[0]:\n",
    "                best.pop()\n",
    "            best.append(a)\n",
    "        return best[-1][2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        la = [0] * (n + 2)\n",
    "        f = [0] * (n + 1)\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            la[i] = max(la[i], la[i-1])\n",
    "            f[i] = f[la[i]] + 1\n",
    "            j = bisect_left(pre, pre[i]*2 - pre[la[i]])\n",
    "            la[j] = i\n",
    "        \n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        q = deque([0])\n",
    "        dp = [0] * (n + 1)\n",
    "        last = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            while len(q) > 1 and s[q[1]] + last[q[1]] <= s[i]:\n",
    "                q.popleft()\n",
    "            dp[i] = dp[q[0]] + 1\n",
    "            last[i] = s[i] - s[q[0]]\n",
    "            while q and s[q[-1]] + last[q[-1]] >= s[i] + last[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        f = [0] * (n + 1)\n",
    "        last = [0] * (n + 1)\n",
    "        q = deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            # 1. 去掉队首无用数据（计算转移时，直接取队首）\n",
    "            while len(q) > 1 and s[q[1]] + last[q[1]] <= s[i]:\n",
    "                q.popleft()\n",
    "            \n",
    "            # 2. 计算转移\n",
    "            f[i] = f[q[0]] + 1\n",
    "            last[i] = s[i] - s[q[0]]\n",
    "            \n",
    "            # 3. 去掉队尾无用数据\n",
    "            while q and s[q[-1]] + last[q[-1]] >= s[i] + last[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return f[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + nums[i]\n",
    "        ans = [0] * (n + 1)\n",
    "        v = [0] * (n + 1)\n",
    "        q = deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            while len(q) > 1 and v[q[1]] <= s[i]:\n",
    "                q.popleft()\n",
    "            ans[i] = ans[q[0]] + 1\n",
    "            last = s[i] - s[q[0]]\n",
    "            while q and v[q[-1]] >= s[i] + last:\n",
    "                q.pop()\n",
    "            v[i] = last + s[i]\n",
    "            q.append(i)\n",
    "        return ans[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        pre_sum = [nn for nn in nums]\n",
    "        for i in range(1, len(nums)):\n",
    "            pre_sum[i] += pre_sum[i - 1]\n",
    "        \n",
    "        dp = deque([[nums[0], 1, 0]])\n",
    "        # unset = set()\n",
    "        cs = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            # print(i, dp)\n",
    "            \n",
    "            \n",
    "            current = pre_sum[i]\n",
    "            c2 = 1\n",
    "\n",
    "            left = 0\n",
    "            right = len(dp) - 1\n",
    "\n",
    "            flag = False\n",
    "            # right ok\n",
    "            cc = pre_sum[i] - pre_sum[dp[right][2]]\n",
    "            cc2 = pre_sum[i] - pre_sum[dp[left][2]]\n",
    "            if cc >= dp[right][0]:\n",
    "                current = cc\n",
    "                c2 = dp[right][1] + 1\n",
    "                flag = True\n",
    "            elif cc2 < dp[left][0]:\n",
    "                flag = True\n",
    "\n",
    "            if not flag:\n",
    "                mid = 0\n",
    "                while left < right - 1:\n",
    "                    mid = (left + right) // 2\n",
    "                    cc = pre_sum[i] - pre_sum[dp[mid][2]]\n",
    "                    if cc >= dp[mid][0]:\n",
    "                        left = mid\n",
    "                    else:\n",
    "                        right = mid\n",
    "                current = pre_sum[i] - pre_sum[dp[left][2]]\n",
    "                c2 = dp[left][1] + 1\n",
    "\n",
    "                print(mid, left, right)\n",
    "         \n",
    "            if c2 > dp[-1][1]:\n",
    "                while dp[0][1] <= c2 - 2:\n",
    "                    dp.popleft()\n",
    "            while dp[-1][0]  >= current + pre_sum[i] - pre_sum[dp[-1][2]]:\n",
    "                dp.pop()\n",
    "                \n",
    "            dp.append([current, c2, i])\n",
    "            \n",
    "        # print(dp)\n",
    "                    \n",
    "                \n",
    "                \n",
    "            \n",
    "            \n",
    "            \n",
    "        return dp[-1][1]\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from string import *\n",
    "from re import *\n",
    "from datetime import *\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from bisect import *\n",
    "from copy import *\n",
    "from math import *\n",
    "from random import *\n",
    "from statistics import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from operator import *\n",
    "from io import *\n",
    "from sys import *\n",
    "from json import *\n",
    "from builtins import *\n",
    "from typing import *\n",
    "\n",
    "\"\"\"\n",
    "You are given a 0-indexed integer array nums.\n",
    "\n",
    "You can perform any number of operations, where each operation involves selecting a subarray of the\n",
    "array and replacing it with the sum of its elements. For example, if the given array is [1,3,5,6]\n",
    "and you select subarray [3,5] the array will convert to [1,8,6].\n",
    "\n",
    "Return the maximum length of a non-decreasing array that can be made after applying operations.\n",
    "\n",
    "A subarray is a contiguous non-empty sequence of elements within an array.\n",
    "\n",
    " \n",
    "\n",
    "Example 1:\n",
    "\n",
    "\n",
    "Input: nums = [5,2,2]\n",
    "Output: 1\n",
    "Explanation: This array with length 3 is not non-decreasing.\n",
    "We have two ways to make the array length two.\n",
    "First, choosing subarray [2,2] converts the array to [5,4].\n",
    "Second, choosing subarray [5,2] converts the array to [7,2].\n",
    "In these two ways the array is not non-decreasing.\n",
    "And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. \n",
    "So the answer is 1.\n",
    "\n",
    "\n",
    "Example 2:\n",
    "\n",
    "\n",
    "Input: nums = [1,2,3,4]\n",
    "Output: 4\n",
    "Explanation: The array is non-decreasing. So the answer is 4.\n",
    "\n",
    "\n",
    "Example 3:\n",
    "\n",
    "\n",
    "Input: nums = [4,3,2,6]\n",
    "Output: 3\n",
    "Explanation: Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing.\n",
    "Because the given array is not non-decreasing, the maximum possible answer is 3.\n",
    "\n",
    " \n",
    "\n",
    "Constraints:\n",
    "\n",
    " * 1 <= nums.length <= 105\n",
    " * 1 <= nums[i] <= 105\n",
    "\"\"\"\n",
    "\n",
    "MOD = 1000000007  # 998244353\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        dp, v, q = [0], [0], deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            while len(q) > 1 and s[q[1]] + v[q[1]] <= s[i]:\n",
    "                q.popleft()\n",
    "            j = q[0]\n",
    "            dp.append(dp[j] + 1)\n",
    "            v.append(s[i] - s[j])\n",
    "            vs = v[-1] + s[i]\n",
    "            while q and s[q[-1]] + v[q[-1]] >= vs:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "testcases = [\n",
    "    # [[272, 482, 115, 925, 983]],\n",
    "    # [[7, 6, 5, 8, 14, 13, 27, 15, 16]],\n",
    "    # [[549, 67, 52, 359, 95, 156, 112, 623]]\n",
    "    # [],\n",
    "]\n",
    "\n",
    "s = Solution()\n",
    "func_name = dir(s)[-1]\n",
    "func = getattr(s, func_name)\n",
    "\n",
    "for args in testcases:\n",
    "    print(func(*args))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        preQueue = curQeueue = deque()\n",
    "        curQeueue.append([0,0,0])\n",
    "\n",
    "        lastDps = []\n",
    "        segment = 0\n",
    "        preSum = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            preSum += num\n",
    "            if curQeueue[0][0] <= preSum:\n",
    "                preQueue = curQeueue\n",
    "                curQeueue = deque()\n",
    "                segment += 1\n",
    "            \n",
    "            while preQueue and preQueue[0][0] <= preSum:\n",
    "                lastDps = preQueue.popleft()\n",
    "\n",
    "            total = preSum - lastDps[2]\n",
    "            mix = total + preSum\n",
    "            \n",
    "            while curQeueue and curQeueue[-1][0] >= mix: curQeueue.pop()\n",
    "            curQeueue.append([mix, total, preSum])\n",
    "        \n",
    "        return segment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        p_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            p_sum[i] = p_sum[i - 1] + nums[i - 1]\n",
    "        f = [0] * (n + 1)\n",
    "        last = [0] * (n + 1)\n",
    "        q, left, right = [0], 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            while left < right and p_sum[q[left + 1]] + last[q[left + 1]] <= p_sum[i]:\n",
    "                left += 1\n",
    "            f[i] = f[q[left]] + 1\n",
    "            last[i] = p_sum[i] - p_sum[q[left]]\n",
    "            while (\n",
    "                right >= left and p_sum[q[right]] + last[q[right]] >= p_sum[i] + last[i]\n",
    "            ):\n",
    "                right -= 1\n",
    "            if right + 1 < len(q):\n",
    "                q[right + 1] = i\n",
    "            else:\n",
    "                q.append(i)\n",
    "            right += 1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = list(accumulate(nums))\n",
    "        last = [0 for _ in nums]\n",
    "        f = [0 for _ in nums]\n",
    "        q = []\n",
    "        l = -1\n",
    "\n",
    "        for i in range(n):\n",
    "            while l+1<len(q) and s[i]>=s[q[l+1]]+last[q[l+1]]:\n",
    "                l+=1\n",
    "            if l>=0:\n",
    "                f[i]=f[q[l]]+1\n",
    "                last[i]=s[i]-s[q[l]]\n",
    "            else:\n",
    "                f[i] = 1\n",
    "                last[i] = s[i]\n",
    "            while q and s[q[-1]]+last[q[-1]]>=s[i]+last[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return f[-1]\n",
    " \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Fenwick:\n",
    "    def __init__(self, n):\n",
    "        self.vs = [(float('-inf'),)*2]*(n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    def _lowbit(self, x):\n",
    "        return x&(-x)\n",
    "    \n",
    "    def update(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.vs[i] = max(self.vs[i], v)\n",
    "            i += self._lowbit(i)\n",
    "    \n",
    "    def query(self, i):\n",
    "        ret = (float('-inf'),)*2\n",
    "        while i:\n",
    "            ret = max(ret, self.vs[i])\n",
    "            i -= self._lowbit(i)\n",
    "        return ret\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        ps, cur = [], 0\n",
    "        for i in range(len(nums)):\n",
    "            cur += nums[i]\n",
    "            ps.append(cur)\n",
    "\n",
    "        tree = Fenwick(len(nums))\n",
    "        tree.update(1, (1, 0))\n",
    "        dp = [(float('-inf'),)*2]*len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            dp[i] = tree.query(i+1)\n",
    "            c, j = dp[i]\n",
    "            t = ps[i]-ps[j]+nums[j]\n",
    "            l, r = i+1, len(nums)-1\n",
    "            while l < r:\n",
    "                mid = l+(r-l)//2\n",
    "                if t > ps[mid]-ps[i]:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    r = mid\n",
    "            if l < len(nums) and t <= ps[l]-ps[i]:\n",
    "                tree.update(l+1, (c+1, i+1))\n",
    "        \n",
    "        return dp[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums) -> int:\n",
    "        ret = 0\n",
    "        N = len(nums)\n",
    "        sums = [0] * (N+1)\n",
    "        for i in range(N):\n",
    "            sums[i+1] = nums[i] + sums[i]\n",
    "\n",
    "        mSums = [0] * (N+1)\n",
    "        cur = nums[0]\n",
    "        t = 0\n",
    "        choice = [0] * N\n",
    "        choice[0] = -1\n",
    "\n",
    "        si = [0] * (N+1)\n",
    "        sv = [0] * (N+1)\n",
    "        si[0] = -1\n",
    "        sv[0] = 0\n",
    "        cs = tt = 0\n",
    "\n",
    "        for i in range(N):\n",
    "            \n",
    "            while t <= cs and sums[i+1]>=sv[t]:\n",
    "                t += 1\n",
    "            t -= 1\n",
    "            mSums[i] = sums[i+1] - sums[si[t]+1]\n",
    "            choice[i] = si[t]\n",
    "\n",
    "            nv = sums[i+1] + mSums[i]\n",
    "            while nv < sv[cs]:\n",
    "                cs -= 1\n",
    "            cs+=1\n",
    "            sv[cs]=nv\n",
    "            si[cs]=i\n",
    "        \n",
    "        t = N-1\n",
    "        while t!=-1:\n",
    "            ret += 1\n",
    "            t = choice[t]\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumLength(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         dps = [[0,0] for _ in range(n + 1)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num >= dps[i][1]:\n",
    "#                 dps[i + 1] = [dps[i][0] + 1, num]\n",
    "#                 print(\"i\",i,\"num\",nums[i],\"tail\",num,\"target\",i - 1)\n",
    "#                 continue\n",
    "#             j = i - 1\n",
    "#             num += nums[j]\n",
    "#             while dps[j][1] > num:\n",
    "#                 j -= 1\n",
    "#                 num += nums[j]\n",
    "#             dps[i + 1] = [dps[j][0] + 1, num]\n",
    "#             print(\"i\",i,\"num\",nums[i],\"tail\",num,\"target\",j - 1)\n",
    "#         print(dps)\n",
    "#         return dps[n][0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial=0))      \n",
    "        dps = [0,1,0,-1] # [结合值, 分段, 尾值, 下标]\n",
    "        heap = []\n",
    "        for i, num in enumerate(nums):\n",
    "            preSum = pre[i + 1]\n",
    "\n",
    "            # 近合并\n",
    "            segment = dps[1]\n",
    "            tailNum = dps[2] + num\n",
    "            \n",
    "            # 远合并\n",
    "            while heap and heap[0][0] <= preSum:\n",
    "                item = heappop(heap)\n",
    "                itemPreSum = item[0] - item[2]\n",
    "                newSegment = item[1] + 1\n",
    "                if newSegment > segment or (newSegment == segment and tailNum > preSum - itemPreSum):\n",
    "                    segment = newSegment\n",
    "                    tailNum = preSum - itemPreSum\n",
    "\n",
    "            # 当前新状态\n",
    "            dps = [tailNum + preSum, segment, tailNum, i]\n",
    "            # print(\"num\",num,dps)\n",
    "\n",
    "            # 放入堆\n",
    "            heappush(heap, dps)\n",
    "\n",
    "        return dps[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0, 0] for _ in range(n + 1)]\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + nums[i]\n",
    "        stk = deque([0])\n",
    "        for i in range(1, n + 1):\n",
    "            while len(stk) > 1 and pre_sum[stk[1]] + dp[stk[1]][1] <= pre_sum[i]:\n",
    "                stk.popleft()\n",
    "            \n",
    "            dp[i][0] = dp[stk[0]][0] + 1\n",
    "            dp[i][1] = pre_sum[i] - pre_sum[stk[0]]\n",
    "\n",
    "            while stk and pre_sum[stk[-1]] + dp[stk[-1]][1] >= pre_sum[i] + dp[i][1]:\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "        return dp[n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        memo = [(0, 0, 0)]\n",
    "        prefix = [0]\n",
    "        \n",
    "        def helper(i) -> int:\n",
    "            ans = 0\n",
    "            l, r = 0, i\n",
    "            while l <= r:\n",
    "                m = l + (r - l) // 2\n",
    "                num = prefix[-1] - prefix[memo[m][1]]\n",
    "                if num >= memo[m][0]:\n",
    "                    ans = m\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            return ans\n",
    "                    \n",
    "        \n",
    "        for i, n in enumerate(nums):\n",
    "            prefix.append(prefix[-1] + n)\n",
    "            j = helper(len(memo) - 1)\n",
    "            num = prefix[-1] - prefix[memo[j][1]]\n",
    "            l = memo[j][2]\n",
    "            while memo and memo[-1][0] + prefix[memo[-1][1]] >= num + prefix[-1]:\n",
    "                memo.pop()\n",
    "            memo.append((num, i + 1, l + 1))\n",
    "            # print(memo)\n",
    "        # print(memo)\n",
    "        return memo[-1][2]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums) -> int:\n",
    "        N = len(nums)\n",
    "        prefix_sum = [0] * (N + 1)\n",
    "        for i in range(N):\n",
    "            prefix_sum[i + 1] = nums[i] + prefix_sum[i]\n",
    "\n",
    "  \n",
    "        end_val = [0] * (N + 1)\n",
    "        end_index = [0] * (N + 1)\n",
    "        end_criteria = [0] * (N + 1)\n",
    "        ans = [0] * (N + 1)      \n",
    "        \n",
    "        cs = 0\n",
    "        ans[0] = 0\n",
    "        end_index[0] = -1\n",
    "        end_val[0] = 0\n",
    "        end_criteria[0] = 0\n",
    "        \n",
    "        ret = 0\n",
    "        start_from = None\n",
    "\n",
    "        for i in range(N):\n",
    "            new_end_index = i\n",
    "            left = 0 if start_from==None else start_from\n",
    "            right = cs\n",
    "            target = 0 if start_from==None else start_from\n",
    "\n",
    "            for mid in range(left, right+1):\n",
    "                if prefix_sum[new_end_index + 1] >= end_criteria[mid]:\n",
    "                    target = mid\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            start_from = target\n",
    "            old_end_index = end_index[target]\n",
    "            new_end_val = prefix_sum[new_end_index + 1] - prefix_sum[old_end_index + 1]\n",
    "            new_end_criteria = new_end_val + prefix_sum[new_end_index + 1]\n",
    "            ans[new_end_index + 1] = ans[old_end_index + 1] + 1\n",
    "            ret = max(ret, ans[new_end_index + 1])\n",
    "            \n",
    "            # keep the criteria increasing\n",
    "            while cs >= 0 and end_criteria[cs] > new_end_criteria:\n",
    "                cs -= 1\n",
    "            \n",
    "            cs += 1\n",
    "            end_index[cs] = new_end_index\n",
    "            end_val[cs] = new_end_val\n",
    "            end_criteria[cs] = new_end_criteria\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, s: List[int]) -> int:\n",
    "        n = len(s)\n",
    "        ss = [0] + list(itertools.accumulate(s))\n",
    "        f = [0] * (n + 1)\n",
    "        st = [(0, 0)]\n",
    "        for i in range(n):\n",
    "            k = st[bisect.bisect_left(st, (ss[i + 1], n)) - 1][1]\n",
    "            f[i + 1] = f[k] + 1\n",
    "            t = 2 * ss[i + 1] - ss[k]\n",
    "            while st and st[-1][0] >= t:\n",
    "                st.pop()\n",
    "            st.append((t, i + 1))\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import bisect\n",
    "\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "# 计算S[1]~S[N]的最长差值递增子序列长度\n",
    "def solve(A: List):\n",
    "    n = len(A)-1\n",
    "\n",
    "    dp = [0] * (n + 1)  # dp[x]表示x位置结尾的合法序列最长长度\n",
    "\n",
    "    stk = []\n",
    "    stk.append((0, 0))  # (A[i] + i号点和其序列中前一个点的差值，结束点i)\n",
    "\n",
    "    for i in range(1, n + 1):\n",
    "        l, r = 0, len(stk) - 1\n",
    "        p = None\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            if stk[mid][0] <= A[i]:\n",
    "                p = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "\n",
    "        dp[i] = dp[stk[p][1]] + 1\n",
    "        key = A[i] + (A[i] - A[stk[p][1]])\n",
    "        while len(stk) and stk[-1][0] >= key:\n",
    "            stk.pop(-1)\n",
    "        stk.append((key, i))\n",
    "\n",
    "    return max(dp[1:])\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        # 后挪一个位置，构造前缀和序列\n",
    "        S = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            S[i] = S[i-1] + nums[i-1]\n",
    "\n",
    "        return solve(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/u/l00/\n",
    "\n",
    "# class Solution:\n",
    "#     def findMaximumLength(self, nums: List[int]) -> int:\n",
    "#         n = len(nums)\n",
    "#         dps = [[0,0] for _ in range(n + 1)]\n",
    "#         for i, num in enumerate(nums):\n",
    "#             if num >= dps[i][1]:\n",
    "#                 dps[i + 1] = [dps[i][0] + 1, num]\n",
    "#                 print(\"i\",i,\"num\",nums[i],\"tail\",num,\"target\",i - 1)\n",
    "#                 continue\n",
    "#             j = i - 1\n",
    "#             num += nums[j]\n",
    "#             while dps[j][1] > num:\n",
    "#                 j -= 1\n",
    "#                 num += nums[j]\n",
    "#             dps[i + 1] = [dps[j][0] + 1, num]\n",
    "#             print(\"i\",i,\"num\",nums[i],\"tail\",num,\"target\",j - 1)\n",
    "#         print(dps)\n",
    "#         return dps[n][0]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums, initial=0))      \n",
    "        dps = [[1,0,-1] for _ in range(n + 1)]\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            if dps[i + 1][2] == -1 or dps[i + 1][0] < dps[i][0] or (dps[i + 1][0] == dps[i][0] and dps[i + 1][1] > dps[i][1] + num):\n",
    "                dps[i + 1] = dps[i].copy()\n",
    "                dps[i + 1][1] += num\n",
    "            segment = dps[i + 1][0] \n",
    "            target = dps[i + 1][1]\n",
    "            if pre[n] - pre[i + 1] < target: continue\n",
    "            left, right = i + 1, n\n",
    "            while left < right:\n",
    "                mid = (left + right) >> 1\n",
    "                if pre[mid + 1] - pre[i + 1] >= target: right = mid\n",
    "                else: left = mid + 1\n",
    "            # if right == n: continue\n",
    "            # print(\"i\",i,\"num\",num,\"right\",right)\n",
    "            if dps[right + 1][2] < i:\n",
    "                dps[right + 1] = [segment + 1, pre[right + 1] - pre[i + 1], i]\n",
    "        # print(dps)\n",
    "        return dps[-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "                          \n",
    "class Solution:\n",
    "    def findMaximumLength(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        s = [0]    #前缀和\n",
    "        for x in nums:\n",
    "            s.append(s[-1] + x)\n",
    "        dp = [[0, inf] for _ in range(n + 1)]\n",
    "        dp[0] = [0, 0]\n",
    "        q = collections.deque([(0, 0)])    \n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            #求满足<= s[i] 的s[j] + last的最右边的j\n",
    "            dp[i] = [dp[i-1][0], dp[i-1][1] + nums[i-1]]\n",
    "\n",
    "            while q and q[0][1] <= s[i]:\n",
    "                j, _ = q.popleft()\n",
    "                dp[i] = [dp[j][0] + 1, s[i] - s[j]] \n",
    "\n",
    "            while q and s[i] + dp[i][1] <= q[-1][1]:\n",
    "                q.pop()\n",
    "\n",
    "            q.append((i, s[i] + dp[i][1]))\n",
    "\n",
    "        return dp[-1][0]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "                \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
